public class List implements Collection {

	private Node begin = null;

	private class Node {

		private Object key;
		private Object element;
		private Node next = null;
		private Node previous = null;

		public Node(Object key, Object element) {
			this.element = element;
			this.key = key;
		}

		public Node(Object key, Object element, Node next, Node prev) {
			this.element = element;
			this.key = key;
			this.next = next;
			this.previous = prev;
		}

		public Object getKey() {
			return key;
		}

		public Object getElement() {
			return element;
		}

		public Node getNext() {
			return next;
		}

		public void setNext(Node next) {
			this.next = next;
		}

		public Node getPrevious() {
			return previous;
		}

		public void setPrevious(Node previous) {
			this.previous = previous;
		}
	}

	private class ListIterator implements Iterator {

		private Node current;

		public ListIterator() {
			this.current = begin;
		}

		public ListIterator(Node begin) {
			this.current = begin;

		}

		@Override
		public Object next() {
			if (current == null) {
				return null;
			} else {
				Node temp = this.current;
				this.current = current.getNext();
				return temp.getKey();
			}
		}

		@Override
		public Object previous() {
			if (current == null) {
				return null;
			} else {
				Node temp = this.current;
				this.current = current.getPrevious();
				return temp.getKey();
			}
		}

		@Override
		public boolean hasNext() {
			return this.current !=null;
		}

		@Override
		public boolean hasPrevious() {
			return this.current.getPrevious()!=null;
		}
	}

	@Override
	public boolean put(Object key, Object element) {
		if (this.isEmpty()) {
			if (this.containsKey(key)) {
				return false;
			}
			this.begin = new Node(key, element, null, null);
		} else {
			if (this.containsKey(key)) {
				return false;
			}
			Node tempLastNode = this.goToLast();
			Node tempNewNode = new Node(key, element);
			tempLastNode.setNext(tempNewNode);
			tempNewNode.setPrevious(tempLastNode);
		}
		return true;
	}

	private Node goToLast() {
		Node tempNode = this.begin;
		while (tempNode.getNext() != null) {
			tempNode = tempNode.getNext();
		}
		return tempNode;
	}
	
	@Override
	public boolean remove(Object key) {
		if (!this.containsKey(key)) {
			return false;
		}
		Node tempNode = this.begin;
		do {
			if (tempNode.getKey().equals(key)) {
				Node tempPrevNode = tempNode.getPrevious();
				Node tempNextNode = tempNode.getNext();
				tempNode.getPrevious().setNext(tempNextNode);
				tempNextNode.setPrevious(tempPrevNode);
				return true;
			}
			tempNode = tempNode.getNext();
		} while (tempNode != null);
		return false;
	}

	@Override
	public boolean containsKey(Object key) {
		if (this.get(key) == null) {
			return false;
		}
		return true;
	}

	@Override
	public boolean containsElement(Object element) {
		if (this.isEmpty()) {
			return false;
		} else {
			Node tempNode = this.begin;
			do {
				if (tempNode.getElement().equals(element)) {
					return true;
				}
				tempNode = tempNode.getNext();
			} while (tempNode != null);
			return false;
		}
	}

	@Override
	public Object get(Object key) {
		if (this.isEmpty()) {
			return null;
		} else {
			Node tempNode = this.begin;
			do {
				if (tempNode.getKey().equals(key)) {
					return tempNode.getElement();
				}
				tempNode = tempNode.getNext();
			} while (tempNode != null);
			return null;
		}
	}
	
	@Override
	public boolean isEmpty() {
		if (begin == null) {
			return true;
		} else {
			return false;
		}
	}

	@Override
	public int getSize() {
		if (begin == null) {
			return 0;
		}
		Node tempNode = begin;
		int i = 1;
		while (tempNode.next != null) {
			i++;
			tempNode = tempNode.next;
		}
		return i;
	}

	@Override
	public Iterator iterator() {
		return new ListIterator(begin);
	}

	public String toString() {
		if (this.isEmpty()) {
			return "EMPTY";
		} else {
			Node tempNode = this.begin;
			String out = "";
			do {
				out += tempNode.getKey() + " | " + tempNode.getElement() + '\n';
				tempNode = tempNode.getNext();
			} while (tempNode != null);
			return out;
		}
	}
}
